A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
The subject invention relates generally to computer systems and more particularly to a software implemented lockless circular buffer.
In the past, emulation software has been employed together with a number of microprocessor chips to emulate mainframe hardware. Such emulation software is comprised of many processes, each of which emulates a piece of prior art hardware, such as a central processor, an I/O processor or a task control unit. The processes request actions from each other by sending messages. Each message is 4 (64-bit) words long. For the system to function properly, the receiving process must receive messages in the order they are sent. Message ordering is critical. For example, a first of two messages might indicate a first value to be written in a disk storage space and the second message an update of that value. If the messages are reversed, the incorrect value will be stored on disk.
The emulator implements message ordering by establishing a circular buffer for each processxe2x80x94a fixed length area where messages are placed when they are sent to the process. Sending processes put messages in each successive slot in the buffer, and the receiving process retrieves them in the same order, according to a first-in, first-out (FIFO) protocol. Thus, each process can have at most a fixed number of messages waiting to be processed.
Several processes can be simultaneously attempting to send a message to a particular process. To prevent the loss of messages, the implementation must ensure that each process uses a unique slot in the buffer. In the prior art, locking mechanisms such as Mutexes, Semaphores, or Critical Regions have been employed to control and order access to the buffer. Such xe2x80x9clockingxe2x80x9d approaches are notoriously slow since one process must wait while another process has a lock on the buffer.
The invention provides a lockless circular buffer. Slots in the buffer are assigned using a counter which is incremented atomically. In this manner, a process can fetch the counter from memory, increment it by 1, and store it back into memory without the possibility of interruption by another process. This xe2x80x9catomicxe2x80x9d operation assures that a unique slot number will be assigned to each process request, even though such requests occur simultaneously. Two counters are kept for each buffer: one contains the number of messages inserted and the other contains the number of messages removed. The number of the last message removed is used to resolve overflow situations where the buffer fills up, resulting in two processes being assigned the same slot number.
Still other objects, features and advantages of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein is shown and described only the preferred embodiment of the invention, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive, and what is intended to be protected by Letters Patent is set forth in the appended claims. The present invention will become apparent when taken in conjunction with the following description and attached drawings, wherein like characters indicate like parts, and which drawings form a part of this application.